<?
include_once "SortHelper/SortHelper.php";
/**
 * 快速排序 2 双路快速排序
 * * i 从左边开始 j 从右边开始
 * 
 * ● 代表 已排好序
 * ○ 代表 待排序
 * 
 * 如果 j 指向的值 < v，i 指向的值 > v，那么 i 和 j 的值就交换位置
 * 
 * arr[l+1...i-1] < v                           arr[j...r] > v
 * v ● ● ● ● ● ● ● ● ●  ○ ○ ○ ○       ○ ○ ○ ○  ● ● ● ● ● ● ●
 * ▲                    ▲                   ▲              ▲
 * l                    i                   j              r
 */

/**
 * 3、对arr[l...r]部分进行partition操作
 * 返回P,使得arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
 */
function _partition(&$arr, $l, $r)
{

    //在将要排序的数组区间随机一个索引
    $rand_index = rand() % ($r - $l + 1) + $l;
    SortHelper::swap($arr, $l, $rand_index);

    //使用最左侧的元素
    $v = $arr[$l];

    /**
     * arr[l+1...i) <= v; arr(j...r]) >= v
     * i 从左边开始
     * j 从右边开始
     */
    $i = $l + 1;
    $j = $r;
    while (true) {

        // 注意这里的边界, arr[i] < v, 不能是arr[i] <= v
        while ($i <= $r && $arr[$i] < $v ) {
            $i++;
        }

        // 注意这里的边界, arr[j] > v, 不能是arr[j] >= v
        while ($j >= $l + 1 && $arr[$j] > $v ) {
            $j--;
        }
        if ($i > $j) {
            break;
        }
        SortHelper::swap($arr, $i, $j);
        $i++;
        $j--;
    }
    SortHelper::swap($arr, $l, $j);

    return $j;
}

//2、递归调用对arr[l...r]的范围进行排序
function quick_sort(&$arr, $l, $r)
{
    if ($l >= $r) {
        return;    
    }

    $p = _partition($arr, $l, $r);
    quick_sort($arr, $l, $p - 1);
    quick_sort($arr, $p + 1, $r);
}

//快速排序 1、主方法
function quickSort(&$arr)
{
    $arr_len = count($arr);
    if ($arr_len <= 0) {
        return [];
    }
    quick_sort($arr, 0, $arr_len - 1);
}

$arr = [100,4,5,6,7,2,44,59,67,57,45,71,82];
quickSort($arr);
for ($i=0; $i < count($arr); $i++) { 
    echo $arr[$i].', ';
}
